package daily.year2025.m1;

import daily.year2024.m8.ListNode;

/**
 * No.143 重排链表
 *
 * @author wjs 2025/1/26
 */
public class d26 {
    class Solution {
        // 三步走
        // 1、将链表拆分两半
        // 2、反转后一半的链表
        // 3、合并两个链表
        public void reorderList(ListNode head) {
            // 1、使用快慢指针找到中间节点
            ListNode quick = head, slow = head, pre = head;
            while(quick != null) {
                pre = slow;
                slow = slow.next;
                quick = quick.next;
                if(quick != null) {
                    quick = quick.next;
                }
            }
            pre.next = null;
            ListNode head2 = slow;
            // 2、反转链表
            head2 = reverseList(head2);
            // 3、合并链表
            ListNode head1 = head;
            while(head2 != null) {
                ListNode next1 = head1.next;
                ListNode next2 = head2.next;
                head1.next = head2;
                head2.next = next1;
                head1 = next1;
                head2 = next2;
            }
        }

        private ListNode reverseList(ListNode head) {
            if(head == null) {
                return null;
            }
            ListNode newHead = null,cur = head, next = head.next;
            while(cur != null) {
                next = cur.next;
                cur.next = newHead;
                newHead = cur;
                cur = next;
            }
            return newHead;
        }
    }
}
